|
In theoretical computer science, in particular in formal language theory, Greibach's theorem states that certain properties of formal language classes are undecidable. It is named after the computer scientist Sheila Greibach, who first proved it in 1963. ==Definitions== Given a set Σ, often called "alphabet", the (infinite) set of all strings built from members of Σ is denoted by Σ *. A formal language is a subset of Σ *. If ''L''1 and ''L''2 are formal languages, their product ''L''1''L''2 is defined as the set of all concatenations of a string ''w''1 from ''L''1 with a string ''w''2 from ''L''2. If ''L'' is a formal language and ''a'' is a symbol from Σ, their quotient ''L''/''a'' is defined as the set of all strings that can be made members of ''L'' by appending an ''a''. Various approaches are known from formal language theory to denote a formal language by a finite description, such as a formal grammar or a finite-state machine. For example, using an alphabet Σ = , the set Σ * consists of all (decimal representations of) natural numbers, with leading zeroes allowed, and the empty string, denoted as ε. The set ''L''div3 of all naturals divisible by 3 is an infinite formal language over Σ; it can be finitely described by the following regular grammar with start symbol ''S''0: : Examples for finite languages are and ; their product yields the even numbers up to 28. The quotient of the set of prime numbers up to 100 by the symbol 7, 4, and 2 yields the language , yields the set of all naturals divisible by 30.---> 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Greibach's theorem」の詳細全文を読む スポンサード リンク
|